package com.leetcode.动态规划;

/**
 * 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
 * 回文字符串 是正着读和倒过来读一样的字符串。
 * 子字符串 是字符串中的由连续字符组成的一个序列。
 * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
 * @author LZF
 *
 */
public class L647回文子串 {
	public static void main(String[] args) {
		int result = countSubstrings("abc");
		System.out.println(result);
	}
	/**
	 * dp[i][j]:以i位置为开始，j位置为结尾的字串是否为回文串，根据定义，i<=j，dp[i][j]才有意义。
	 * if(s[i] == s[j]) 则判断dp[i+1][j-1]是否回文串
	 * 当i==j时，dp[i][j]=true，（一个字符）是回文串
	 * 当i = j -1时，dp[i][j]= (s[i] == s[j])
	 * 
	 * 遍历顺序，因为dp[i][j]受dp[i+1][j-1]的影响，因此i需要从最大遍历最小，也就是倒叙，j可以从最小遍历到最大，也就是正序
	 */
	public static int countSubstrings(String s) {
		boolean[][] dp = new boolean[s.length()][s.length()];
		int result = 0;
		for(int i = s.length() - 1;i >= 0;i--) {
			for(int j = i;j < s.length();j++) {
				if(i == j) dp[i][j] = true;
				else if(i == j - 1) dp[i][j] = s.charAt(i) == s.charAt(j);
				else dp[i][j] = (s.charAt(i) == s.charAt(j)) ? dp[i + 1][j - 1] : false;
				if(dp[i][j]) result++;
			}
		}
		return result;
    }
}
